In a typical wireless communication system, error correction is introduced to address the problem of distortion caused by the communication channel. Low-density parity-check (LDPC) codes form a class of error-correcting codes. With the near-Shannon-limit performance, LDPC codes have become promising candidate codes for current and future-generation wireless systems. For example, they have been adopted for wireless local area network (WLAN), wireless metropolitan area networks (WMAN) and satellite TV in IEEE 802.11n, IEEE 802.16e (WiMAX) and DVB-S2 standards, respectively. In addition, LDPC codes can be used in data storage for encoding and decoding data.
FIG. 1 depicts a fundamental communication system using LDPC codes. The k data bits {d0, d1, . . . , dk−1} are first passed to the LDPC encoder 10. For a given m×n parity-check matrix H 11, m redundant bits {p0, p1, . . . , pm−1} are evaluated based on the data bits and then taken as the parity bits. A codeword c with length n (n=k+m) is subsequently formed by the k data bits and the m parity bits. After that, modulation 12 is performed before data transmission via the communication channel 13. After demodulation 14, based on the received signals, the LDPC decoder 15 estimates the data bits by finding a codeword ĉ such that HĉT=0, where T represents the transpose operator that interchanges the columns and rows. After the transpose operation, the element in the ith row and jth column of the original matrix will become the element in the ith column and jth row of the new matrix.
Referring to FIG. 1, the design of the LDPC coding system involves the generation of the parity-check matrix H 11, and the implementations of the encoder 10 and the decoder 15. If there are no hardware constraints, the simplest method to create a sparse parity-check matrix H is to place 1's randomly and sparsely in H. However, in order to evaluate the generator matrix G with GHT=0, Gaussian elimination needs to be performed to convert H into the systematic form Hsys=[Q|I], where Q is an m×k matrix and I is an m×m identity matrix with 1's on the diagonal and 0's elsewhere, such that the generator matrix G=[I|QT] can be found. Therefore, if H is constructed randomly, after the transformation, the sparseness of the original parity-check matrix H will disappear in the resulting matrix Hsys. Also, the resulting matrix Hsys may not have m independent rows. To overcome these problems, H is often established directly in some specific forms. For example, in the publication by Li et al., “Low density parity check codes with semi-random parity check matrix”, Electronics Letters, Vol. 35, No. 1, January 1999, pp. 38-39, H is divided into two sparse matrices H1 and H2. H=[H1|H2] where H1 is an m×k matrix corresponding to the data bits of the codeword and H2 is a full-rank m×m matrix corresponding to the parity bits. The systematic generator matrix for the encoder to generate the redundant bits is obtained by Gsys=[I|H1H2−T]. Since Gsys is not sparse, evaluating the redundant bits using Gsys directly involves a lot of computations. Alternatively, if the matrix H2 can be constructed in a lower triangular form, the parity part of the codeword pl, l=0, 1, . . . , m−1, can be solved recursively such that the evaluation of the generator matrix Gsys will be unnecessary. Generally, H2 is taken to be a dual-diagonal matrix with non-zero elements located on the dual diagonal and zero elsewhere, and is given by:
                              H          2                =                              [                                                            1                                                  0                                                  0                                                  0                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                                              1                                                  1                                                  0                                                  0                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                                              0                                                  1                                                  1                                                  0                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                                              0                                                  0                                                  1                                                  1                                                  0                                                  ⋯                                                  0                                                  0                                                  0                                                                              ⋮                                                  ⋮                                                  ⋮                                                  ⋮                                                  ⋮                                                  ⋱                                                  ⋮                                                  ⋮                                                  ⋮                                                                              0                                                  0                                                  0                                                  0                                                  0                                                  ⋯                                                  1                                                  0                                                  0                                                                              0                                                  0                                                  0                                                  0                                                  0                                                  ⋯                                                  1                                                  1                                                  0                                                                              0                                                  0                                                  0                                                  0                                                  0                                                  ⋯                                                  0                                                  1                                                  1                                                      ]                    .                                    (        1        )            
The weight of a column is defined as the number of non-zero entries in a column. In the matrix H2 in Equation (1), all columns have a weight of two except the last column which has a weight of one.
To further facilitate the implementations of the encoder and the decoder, block-structured LDPC codes are considered for practical applications. A block-structured LDPC code is represented by a “base parity-check matrix” Hb, in which each element is a square sub-block matrix of size z by z, and z is an integer defined as the expansion factor. Compared with the parity-check matrix H, a base parity-check matrix Hb has a much smaller size (reduced by z times z) and therefore requires much less memory for storage. Furthermore, a base matrix Hb can be easily and flexibly expanded to a parity-check matrix H for different code lengths by using sub-block matrices with appropriate sizes.
Referring to FIG. 2, the structure of an LDPC code consisting of sub-block matrices is shown. Each of the sub-block matrices is a square sub-block matrix of size z by z. For the data portion H1 of the parity-check matrix, each of the sub-block matrices inside can be a zero matrix 0, an identity matrix I or a permutation matrix P. For the parity portion H2 of the parity-check matrix, each of the sub-block matrices in the lower triangular area 20 can be a zero matrix 0, an identity matrix I or a permutation matrix P while the sub-block matrices 21 not in the lower triangular area 20 must be zero matrices 0. All sub-block matrices on the diagonal 22 of H2 are identity matrices I. Except the last sub-block column 23 which contains only one non-zero sub-block matrix, each of the other sub-block columns in H2 contains two or more non-zero sub-block matrices. The fully-expanded matrix H2 exists when the sub-block matrices are replaced by actual 0's and 1's. The last z columns in the fully-expanded matrix H2 have weights of one. This is undesirable, particularly for a large value of z, because the larger the number of columns with a weight of one, the worse the error-correction capability of the LDPC code. To avoid the existence of a large number of columns with a weight of one in the fully-expanded matrix H2, the structure of H2 in FIG. 2 should be modified.
Referring to FIG. 3, another structure of an LDPC code consisting of sub-block matrices is shown. The dual-diagonal 30 structure of H2 contains sub-block matrices, except the first sub-block column which contains three non-zero sub-block matrices 31 (each individual column inside the first sub-block column when H2 is fully-expanded will then have a weight of three), all other sub-block columns contain two non-zero sub-block matrices (each individual column inside these sub-block columns when H2 is fully-expanded will then have a weight of two). For the sub-block columns containing two non-zero sub-block matrices, the non-zero sub-block matrices are located at the dual-diagonal 30 positions of H2 (as in FIG. 3) and are commonly fixed as identity matrices I.
Depending on the uniform (constant) or non-uniform (non-constant) weights of the parity-check matrix H, the LDPC codes can be classified into regular or irregular codes. The regular codes have constant column weight and constant row weight, whereas the irregular codes are characterized by unequal column weights and/or unequal row weights.
In the prior art it has been shown that in terms of error performance, the optimal column weights should be non-uniform while the row weights should be nearly-uniform with only two or three consecutive weight values. Therefore, to achieve a lower error rate, a parity-check matrix H with non-uniform column weights and nearly-uniform row weights is preferred. Consider the case when H is expressed in the form H=[H1|H2]. Then, the column weights of H1 and/or H2 should be non-uniform. When both the column weights of H1 and H2 are uniform, they should then be unequal. Furthermore, the row weights of H1, H2 and H are usually designed to be as uniform as possible. An example of an LDPC code with such features is shown in FIG. 3, which has been presented in the IEEE 802.16e standard. In FIG. 3, the column weights of H1 are non-uniform and those of H2 32 are nearly-uniform. The row weights of all H1, H2 and H=[H1|H2] are nearly-uniform. Also in FIG. 3, the parity portion 32 of the parity-check matrix is in a completely deterministic form for all the columns which have a weight of two.